#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=57 lang=cpp
 *
 * [57] 插入区间
 */

// @lc code=start
class Solution
{
public:
    // vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    //     vector<vector<int>> res; int l, r; bool flag = false;
    //     for (int i = 0; i < intervals.size(); i++) {
    //         if (!flag && intervals[i][1] >= newInterval[0]) {
    //             if (newInterval[1] < intervals[i][0]) {
    //                 res.push_back(newInterval); res.push_back(intervals[i]);
    //             }
    //             else {
    //                 res.push_back({min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])});
    //             }
    //             flag = true;
    //         } else {
    //             if (i == 0  || !flag) res.push_back(intervals[i]);
    //             else if (intervals[i][0] <= res.back()[1]) {
    //                 res.back()[1] = max(intervals[i][1], res.back()[1]);
    //             }
    //             else res.push_back(intervals[i]);
    //         }
    //     }
    //     if (!flag) res.push_back(newInterval);
    //     return res;
    // }

    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        bool flag = false;
        vector<vector<int>> res;
        for (int i = 0; i < intervals.size(); i++)
        {
            if (!flag && intervals[i][0] >= newInterval[0])
            {
                if (!res.size() || newInterval[0] > res.back()[1])
                    res.push_back(newInterval);
                else
                {
                    res.back()[1] = max(res.back()[1], newInterval[1]);
                }
                i--;
                flag = true;
            }
            else if (flag)
            {
                if (intervals[i][0] > res.back()[1])
                    res.push_back(intervals[i]);
                else
                    res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }
        if (!flag)
        {
            if (!res.size() || newInterval[0] > res.back()[1])
                res.push_back(newInterval);
            else
            {
                res.back()[1] = max(res.back()[1], newInterval[1]);
            }
        }
        return res;
    }
};
// @lc code=end
